



<HTML>

<HEAD>

<LINK rel="stylesheet" href="../exer.css">

</HEAD>

<BODY>

<H1>

Data Structures, Algorithms, & Applications in C++<BR>

Chapter 7, Exercise 1<BR>

<BR>

</H1>

The code for the new class is given below and in the files

<code class=var>solist.*</code>.

<br><br>

<HR class = coderule>

<pre class = code>

template&lt;class E, class K&gt;

class SortedList {

   public:

      SortedList(int MaxListSize = 10); // constructor

      ~SortedList() {delete [] element;} // destructor

      bool IsEmpty() const {return length == 0;}

      int Length() const {return length;}

      bool Search(const K&amp; k, E&amp; e) const;

      SortedList&lt;E,K&gt;&amp; Delete(const K&amp; k, E&amp; e);

      SortedList&lt;E,K&gt;&amp; Insert(const E&amp; e);

      SortedList&lt;E,K&gt;&amp; DistinctInsert(const E&amp; e);

      void Output(ostream&amp; out) const;

   private:

      int length;

      int MaxSize;

      E *element; // dynamic 1D array

};



template&lt;class E, class K&gt;

SortedList&lt;E,K&gt;::SortedList(int MaxListSize)

{// Constructor for formula-based sorted list.

   MaxSize = MaxListSize;

   element = new E [MaxSize];

   length = 0;

}



template&lt;class E, class K&gt;

bool SortedList&lt;E,K&gt;::Search(const K&amp; k, E&amp; e) const

{// Put element that matches k in e.

 // Return false if no match.

   // examine elements from left to right

   int i = 0;

   while (i &lt; length &amp;&amp; k &gt; element[i])

      i++;



   // verify match

   if (i &gt;= length || k != element[i]) return false;



   // there is a match

   e = element[i];

   return true;

 }



template&lt;class E, class K&gt;

SortedList&lt;E,K&gt;&amp; SortedList&lt;E,K&gt;::

                 Delete(const K&amp; k, E&amp; e)

{// Delete element that matches k.

 // Return deleted element in e.

 // Throw BadInput exception if no match.



   // search for matching element

   int i = 0;

   while (i &lt; length &amp;&amp; k &gt; element[i])

      i++;



   // verify match

   if (i &gt;= length || k != element[i])

      throw BadInput();  // no match



   // put matching element in e and delete

   e = element[i];

   for (int j = i + 1; j &lt; length; j++)

      // shift element left by one

      element[j-1] = element[j];

   length--;  // new list length



   return *this;

}



template&lt;class E, class K&gt;

SortedList&lt;E,K&gt;&amp; SortedList&lt;E,K&gt;::

                 Insert(const E&amp; e)

{// Insert e.  Throw NoMem exception if no space.

   if (length == MaxSize) throw NoMem();



   // find proper place to insert

   // when done, insert to left of element[i]

   int i = 0;

   while (i &lt; length &amp;&amp; e &gt; element[i])

      i++;



   // move element[i:length - 1] one spot right

   for (int j = length-1; j &gt;= i; j--)

      element[j+1] = element[j];



   // insert e

   element[i] = e;

   length++;



   return *this;

}



template&lt;class E, class K&gt;

SortedList&lt;E,K&gt;&amp; SortedList&lt;E,K&gt;::

                 DistinctInsert(const E&amp; e)

{// Insert e only if no matching element present.

 // Throw BadInput exception if duplicate.

 // Throw NoMem exception if no space.



   // find proper place to insert

   // when done, insert to left of element[i]

   int i = 0;

   while (i &lt; length &amp;&amp; e &gt; element[i])

      i++;

   

   // check if duplicate

   if (i &lt; length &amp;&amp; e == element[i])

      throw BadInput();  // duplicate



   // make sure we have space for new element

   if (length == MaxSize) throw NoMem();



   // move element[i:length - 1] one spot right

   for (int j = length-1; j &gt;= i; j--)

      element[j+1] = element[j];



   // insert e

   element[i] = e;

   length++;



   return *this;

}



template&lt;class E, class K&gt;

void SortedList&lt;E,K&gt;::Output(ostream&amp; out) const

{// Put the list into the stream out.

   for (int i = 0; i &lt; length; i++)

      out &lt;&lt; element[i] &lt;&lt; "  ";

}



// overload &lt;&lt;

template &lt;class E, class K&gt;

ostream&amp; operator&lt;&lt;(ostream&amp; out,

         const SortedList&lt;E,K&gt;&amp; x)

   {x.Output(out); return out;}

<hr class=coderule>

</pre>





</FONT>

</BODY>

</HTML>

